package cn.zzf.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <pre>{@code
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 *
 * 示例 2：
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 *
 * 示例 3：
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 *
 * 提示：
 * 3 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 * }</pre>
 *
 * @author zzf
 * @date 2025-06-04 10:18
 */
public class T0015_ThreeSum {

    /*public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] array = Arrays.stream(nums).sorted().toArray();
        int maxIdx = array.length - 1;
        // 都大于0或者都小于0直接返回空数组
        if (array[0] > 0 || array[maxIdx] < 0) return res;

        int iLeft = 0, iRight = maxIdx;

        while (iRight > iLeft) {
            int vLeft = array[iLeft];
            int vRight = array[iRight];

            if (vLeft > 0 || vRight < 0) {
                break;
            }

            int iTmp, step;
            boolean lessZero;

            if (vLeft + vRight > 0) {
                iTmp = iLeft + 1;
                step = 1;
                lessZero = false;
            } else {
                iTmp = iRight - 1;
                step = -1;
                lessZero = true;
            }
            boolean leftAdd = false, rightAdd = false;

            while (true) {
                int vTmp = array[iTmp];
                if (iTmp >= iRight) {
                    leftAdd = true;
                    break;
                }
                if (iTmp <= iLeft) {
                    rightAdd = true;
                    break;
                }
                if (vLeft + vRight + vTmp < 0 && lessZero) {
                    // 本来小于0，现在+最大的数还是小于0，说明没有遇到=0的值或者vLeft太大了两个right加起来都比不上，停止遍历。反之亦然
                    // 比如 -100 -1 0 1 2 3，我们发现-100 + 3 + 2 < 0，就没必要继续了
                    leftAdd = true;
                    break;
                } else if (vLeft + vRight + vTmp > 0 && !lessZero) {
                    rightAdd = true;
                    break;
                } else if (vLeft + vRight + vTmp != 0) {
                    iTmp += step;
                } else {
                    // = 0
                    res.add(Arrays.asList(vLeft, vTmp, vRight));
                    if (lessZero) {
                        leftAdd = true;
                    } else {
                        rightAdd = true;
                    }
                    break;
                }
            }
            if (leftAdd) {
                do {
                    iLeft++;
                } while (iLeft < iRight && array[iLeft] == vLeft);
            }
            if (rightAdd) {
                do {
                    iRight--;
                } while (iLeft < iRight && array[iRight] == vRight);

            }
        }
        return res;
    }*/


    /*public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] array = Arrays.stream(nums).sorted().toArray();
        int maxIdx = array.length - 1;
        // 都大于0或者都小于0直接返回空数组
        if (array[0] > 0 || array[maxIdx] < 0) return res;

        boolean leftAdd = false, rightAdd = false;

        for (int iLeft = 0; iLeft < maxIdx; ) {
            int vLeft = array[iLeft];
            if (vLeft > 0) break;
            for (int iRight = maxIdx; iRight > 0; iRight--) {
                int vRight = array[iRight];
                if (vRight < 0) break;

                int iTmp, step;
                boolean lessZero;

                if (vLeft + vRight > 0) {
                    iTmp = iLeft + 1;
                    step = 1;
                    lessZero = false;
                } else {
                    iTmp = iRight - 1;
                    step = -1;
                    lessZero = true;
                }
                while (iTmp < iRight && iTmp > iLeft) {
                    int vTmp = array[iTmp];
                    if (vLeft + vRight + vTmp < 0 && lessZero) {
                        // 本来小于0，现在+最大的数还是小于0，说明没有遇到=0的值或者vLeft太大了两个right加起来都比不上，停止遍历。反之亦然
                        // 比如 -100 -1 0 1 2 3，我们发现-100 + 3 + 2 < 0，就没必要继续了
                        leftAdd = true;
                        break;
                    } else if (vLeft + vRight + vTmp < 0 && !lessZero) {
                        rightAdd = true;
                        break;
                    } else if (vLeft + vRight + vTmp != 0) {
                        iTmp += step;
                    } else {
                        // = 0
                        res.add(Arrays.asList(vLeft, vTmp, vRight));

                    }
                }
            }
            do {
                iLeft++;
            } while (iLeft < array.length - 1 && array[iLeft] == vLeft);

        }
        return res;
    }*/

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i > 0 && x == nums[i - 1]) continue; // 跳过重复数字
            if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
            if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                } else if (s < 0) {
                    j++;
                } else { // 三数之和为 0
                    ans.add(List.of(x, nums[j], nums[k]));
                    for (j++; j < k && nums[j] == nums[j - 1]; j++); // 跳过重复数字
                    for (k--; k > j && nums[k] == nums[k + 1]; k--); // 跳过重复数字
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-2, 0, 1, 1, 2}));
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }

}
